Strong technology advances in such critical areas as medicine, reliable infrastructure, and security will require strong progress in the development of computational systems able to support the engineering these new technologies will require. Today, engineering methods are ineffective for the most complex and advanced systems foreseen for these areas because of ungainly analytical methods or the complete lack of systematic approaches to designing these systems. This situation was foreshadowed in the middle of the 20th Century by the near simultaneous mathematical discoveries of Kurt Gödel and Alan Turing that many problems thought to be addressable by mathematical means could actually never be solved by mathematics. A more intuitive version of what Gödel had called a formal system was defined by Turing in what is known as a Turing Machine (a TM), the archetype of today's digital computers. Turing and others showed that, while all problems subject to computation could be solved with TMs, many of the key problems that need to be solved for the great advances simply cannot be addressed by them or any variant that they could think of. This conclusion has come to be seen, not as a correctable weakness in current computer capabilities, but as profound limitation of mathematics itself. So computers, to the extent that they derive their methods from mathematics alone, may be inadequate no matter how thoroughly they are developed.
Most of the critical computational problems today fall into two sorts: 1) problems for which algorithms are known but take too much time or computational memory to produce useful results with practical resources; these are known as “intractable” problems; and 2) problems which have been proven to be intrinsically unsolvable by computation. The second types of problem are the non-computable problems because recursive functions that solve the problems cannot be found. Such problems are sometimes referred to as “non-recursive” or “non-computable”. Vital but intractable and non-recursive problems arise in such endeavors as nanotechnology with complex many-body interactions; bioinformatics where near infinite combinations and permutations must be examined one by one; and individualized medicine, which requires the matching an individual's genetic material, DNA, RNA, and other complex molecules with equally complex therapeutic alternatives.
Less challenging, but perhaps much more urgently needed is the validation and verification of large networked computer programs that run critical social, economic, and defense systems. To date, the best known algorithms and physically realizable computational models indicate that no ordinary computer can make decisive contributions to, much less solve these problems. And while there was hope for a while that the quantum computers, under development in many labs around the world for the past generation, and so tantalizingly near today, would offer crucial breakthroughs, the widely accepted conclusions among specialists is that the quantum computers envisioned today will be no different. These powerful quantum machines, with their lightning speed will put a serious dent in the intractability challenge because they are so fast. In the end, however, they can do no more than mathematics itself. While exponentially faster, quantum computers are impotent in the face of non-recursive problems. Quantum computers can expand the classes of problems that are tractable for solution by TMs, but they cannot expand the classes of problems that are computable.
In many settings, the precise solution merely bestows an economic advantage on those able to find the correct answer. Economic advantage, while a respected attribute within advanced market economies, seldom commands the sometimes large resources required to reach exact solutions. However, there are scenarios where price elasticity is much steeper and thus the claim on attention and resources much greater. These inelastic scenarios include, on a personal level, for example, mapping individual DNA into a precisely customized therapy—something for which the individual would be willing to pay a premium price even if the society would tolerate a lower one. On a social level, inelastic scenarios arise from existential threats. Well-known examples are cryptology and verification and validation (V & V) of critical software, the prime factorization problem, and the halting problem, respectively. Consider such cases as the deciphering of messages between terrorist cells or certifying software for a large nuclear plant or an air traffic system. Society would be willing to pay a premium for these accomplishments.